#力扣29 两数相除

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 处理符号
        sign = -1 if (dividend < 0) ^ (divisor < 0) else 1

        abs_dividend = abs(dividend)
        abs_divisor = abs(divisor)

        result = 0

        while abs_dividend >= abs_divisor:
            temp_divisor = abs_divisor
            multiple = 1
            # 找到最大的倍数，使得 temp_divisor * 2^multiple <= abs_dividend
            while (temp_divisor << 1) <= abs_dividend:
                temp_divisor <<= 1
                multiple <<= 1
            result += multiple
            abs_dividend -= temp_divisor

        ans = sign * result

        # 处理溢出情况
        max_int = 2 ** 31 - 1
        min_int = - (2 ** 31)
        if ans < min_int:
            return min_int
        elif ans > max_int:
            return max_int
        else:
            return ans